1. Technical Field Text
The present invention relates to arithmetic coding and in particular to arithmetic coding which adaptively estimates a probability to accurately account for the probability in a finite precision environment and limit the ratio of symbols to bits representative of the symbols.
2. Background Information
Arithmetic coding has been successfully applied to compression of media data such as images, and audio. The newest video coding standard H.264/AVC proposed by the ITU-T and MPEG, which is incorporated herein by reference, achieves a significant performance improvement over previous coding standards such as H.263 and MPEG 2. H.264/AVC standard supports two different entropy coding methods, i.e., Context-based Adaptive Variable Length Coding (CAVLC) and Context-based Adaptive Binary Arithmetic Coding (CABAC). Compared with CAVLC, CABAC provides higher coding efficiency at average bit rate saving of 9%-14%. See Li Liu and Xinhua Zhuang “CABAC Based Bit Estimation for First H.264 Rd Optimization Decision,” IEEE, 2009, which is incorporated herein by reference.
The basic idea of the CABAC encoding process is recursive interval division. The CABAC engine keeps two registers. The first register is a range register with 9-bits. The second register is an offset register which is 9-bits in a regular mode and 10-bits in a bypass mode. The range register keeps track of the width of the current interval. The offset is from the bit-stream and points to the current location within the range. When decoding a bin, the range is divided into two subintervals depending on the probability of occurrence unique to the bin. After the bin is decoded, the range and offset are updated. After decoding one bin, range and offset will be renormalized to keep the precision to decode a next bin. It ensures the most significant bit of the 9 bit register range is always 1.
Although theories have shown that CABAC is an efficient coding method, practical implementation of CABAC poses some technical issues, particularly when a symbol to be coded has a high probability of occurrence. For example, in the CABAC coding engine in which calculations are performed on numbers whose digits of precision are limited by the available lengths of registers for use in calculations, the highest probability represented by the coding model is limited by the finite precision constraints. The finite precision constraints prevent symbols with high probabilities of occurrence from being coded efficiently, since the high probabilities cannot be accurately represented in the finite precision environment. Also, in CABAC, symbols with high probabilities of occurrences are compressed to a high degree, and thus fewer bits are necessary to encode symbols with high probability of occurrence. However, the video decoding performance of a decoder is typically evaluated by the number of bits processed within a predetermined time period. If a large number of symbols are encoded in a small number of bits, although the CABAC decoding speed improves, the overall processing speed at a decoder deteriorates.
Symbols with low probabilities of occurrence also present technical challenges in practical implementation of CABAC. Integer symbols used in MPEG, e.g., transform coefficients and motion vector differences, can be modeled by the following geometric distribution:p(k)=(1−p)k−1×p where k is the absolute value of a symbol, p is the model parameter, and p(k) is the probability of occurrence of the symbol. This type of distribution is amenable to binary arithmetic coding under CABAC, in which the value k is encoded using k−1 binary symbols A followed by one binary symbol B. For an ideal arithmetic coder and for a stationary source with a known parameter p, the expected number of bits required to encode the value k is equal to−(k−1)×log2(1−p)−log2p. 
In practical implementation, since the parameter p is usually not known, and the source may be non-stationary, the parameter p is adaptively estimated based on the frequencies of the respective binary symbols. Although H.264/AVC provides adaptive estimation techniques with which the parameter p is conveniently estimated, they operate at the cost of coding efficiency penalty. In a CABAC coding engine which adaptively estimates the parameter p, the number of bits used to encode the value k from stationary source can be approximated by−(k−1)×log2(1p)−log2p+k×z z has a value in the range of 0.01 to 0.02 and represents an inefficiency associated with the estimation process. Given that an expected value of k may be expressed by 1/p, the above equation becomes
            -                        1          -          p                p              ×                  log        2            ⁡              (                  1          -          p                )              -            log      2        ⁢    p    +            z      p        .  Thus, as the parameter p becomes small, the inefficiency associated with z is increased, and the number of bits used to encode the value k becomes significantly larger than the theoretically required number of bits. In other words, as the parameter p becomes small, the arithmetic coder is no longer able to efficiently compress the symbol. Furthermore, the inefficiency is aggregated by the constraints posed by the finite precision environment, i.e., the inability to perform accurate coding calculations when the parameter p is small.
To address these issues, H.264/AVC has introduced a threshold value t in the coding process. If the value of k is smaller than or equal to the threshold value t, the value of k is encoded using k−1 binary symbols A followed by one binary symbol B. If the value of k is larger than the threshold value t, the value k is encoded using t symbols A followed by an escape sequence representing k minus t. In H.264/AVC, the escape sequence is formed by the exponential Golomb coding. However, this solution is sub-optimal because the threshold t is predetermined in an ad-hoc fashion, and the structure of the escape sequence may not accurately represent the statistical properties of the source.